﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0132_InsertIntoBST : IAlgorithm
    {
        // 701. 二叉搜索树中的插入操作

        // 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。
        // 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
        // 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

        // 提示：
        //  树中的节点数将在[0, 10^4] 的范围内。
        //  -10^8 <= Node.val <= 10^8
        //  所有值 Node.val 是 独一无二 的。
        //  -10^8 <= val <= 10^8
        //  保证 val 在原始BST中不存在。


        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
        }

        // 算法
        public TreeNode InsertIntoBST(TreeNode root, int val)
        {
            if (root == null)
                return new TreeNode(val);
            var temp = root;
            while (temp!= null)
            {
                if (temp.val > val)
                    if (temp.left == null)
                    {
                        temp.left = new TreeNode(val);
                        break;
                    }
                    else
                        temp = temp.left;
                else
                    if (temp.right == null)
                    {
                        temp.right = new TreeNode(val);
                        break;
                    }else
                    temp = temp.right;

            }
            return root;
        }
    }
}
